package top.humbleyuan.sortmethod;

import java.lang.reflect.InvocationHandler;
import java.lang.reflect.Proxy;
import java.util.Arrays;

/**
 * @Author HumbleYuan
 * @Date 2020/2/15 15:10
 * @Des 快速排序
 */
public class Quick {
    public static void main(String[] args) {
        int[] array = {3,12,14,3,6,1,9,8,7};

        quickSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }


    public static void quickSort(int[] arr,int low,int high){
        int i, j, temp;

        // 无中间元素
        if(low > high){
            return;
        }


        // 左右哨兵分配位置
        i = low;
        j = high;

        // temp就是基准位，这里选最低位为基准位
        temp = arr[low];

        // 左右哨兵相遇后跳出
        while (i < j) {
            // 高位找第一个小于基准位的数的index:j
            while (temp <= arr[j] && i < j) {
                j--;
            }
            // 低位找第一个大于基准位的数的index：i
            while (temp >= arr[i] && i < j) {
                i++;
            }
            // 如果满足条件则交换
            if (i < j) {
                swap(arr, i, j);
            }
        }

        // 最后将基准位与i和j相等位置的数字交换
        swap(arr, low, i);

        //递归调用左半数组
        quickSort(arr, low, j-1);
        //递归调用右半数组
        quickSort(arr, j+1, high);
    }

    // 交换数组中两数位置
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
